﻿//1.小美的平衡矩阵
//小美拿到了一个𝑛∗𝑛的矩阵，其中每个元素是 0 或者 1。
//小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
//现在，小美希望你回答有多少个i∗i的完美矩形区域。你需要回答1≤i≤n的所有答案。

#include<iostream>

using namespace std;
const int N = 210;

int g[N][N];
int s[N][N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string str;
        cin >> str;
        int k = 0;
        for (int j = 1; j <= n; j++)
        {
            g[i][j] = str[k++] - '0';
            //1的数量
            s[i][j] = g[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (i % 2)
        {
            cout << "0" << '\n';
            continue;
        }
        int res = 0;
        for (int j = i; j <= n; j++)
        {
            for (int k = i; k <= n; k++)
            {
                int sum = s[j][k] - s[j][k - i] - s[j - i][k] + s[j - i][k - i];
                if (sum == (i * i) / 2)res++;
            }
        }
        cout << res << '\n';
    }
}



//2.小美的数组询问
//小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
//现在小美想知道，如果那些未知的元素在区间[l, r]范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？
//共有q次询问。

#include <iostream>
#include <vector>
using namespace std;

long long know_sum = 0;
long long unknow_num = 0;

void func(int left, int right)
{
    long long min = know_sum + unknow_num * left;
    long long max = know_sum + unknow_num * right;
    cout << min << " " << max << endl;
}


int main()
{
    long long n, q;
    cin >> n;
    cin >> q;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        if (arr[i])
        {
            know_sum += arr[i];
        }
        else {
            unknow_num++;
        }
    }

    for (int i = 0; i < q; i++)
    {
        long long left, right;
        cin >> left;
        cin >> right;
        func(left, right);
    }
    return 0;
}



//3.小美的 MT
//MT 是美团的缩写，因此小美很喜欢这两个字母。
//现在小美拿到了一个仅由大写字母组成字符串，她可以最多操作k次
//每次可以修改任意一个字符。小美想知道，操作结束后最多共有多少个'M'和'T'字符？

#include <iostream>
using namespace std;

int main()
{
    string s;
    int n, k;
    cin >> n >> k;
    cin >> s;
    int ret = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'M' || s[i] == 'T')
        {
            ret++;
        }
    }
    ret += k;
    if (ret > n)
    {
        ret = n;
    }
    cout << ret << endl;
    return 0;
}



//4.小美的朋友关系
//小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。
//现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？
//事件共有 2 种：
//1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
//2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。
//注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

//并查集
map<int, int> fa;

typedef struct
{
    int op;
    int u;
    int v;
}node;

int find(int x)
{
    while (fa[x] != x) x = fa[x] = fa[fa[x]];
    return x;
}
void merge(int u, int v)
{
    int u_fa = find(u);
    int v_fa = find(v);
    if (u_fa != v_fa)
        fa[u_fa] = v_fa;
}

int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    set<pair<int, int>>  st;    //关系集合 

    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        st.insert({ u,v });     //存储关系
        fa[u] = u;
        fa[v] = v;
    }
    node OP[q];
    int num = 0;
    for (int i = 0; i < q; i++) {
        int op, u, v; cin >> op >> u >> v;
        //查询操作，可以直接存入
        if (op == 1) {
            if (st.find({ u, v }) != st.end()) st.erase({ u, v });
            else if (st.find({ v, u }) != st.end()) st.erase({ v, u });
            else continue;
        }
        // 存入新的操作数组中
        OP[num++] = { op, u, v };
    }
    //建立并查集
    for (auto& e : st)
    {
        int u = e.first;
        int v = e.second;
        merge(u, v);
    }
    vector<bool> ret;
    for (int i = num - 1; i >= 0; i--)
    {
        int op = OP[i].op, u = OP[i].u, v = OP[i].v;
        if (op == 1)
        {
            merge(u, v);
        }
        else
        {
            if (!fa[u]) fa[u] = u;
            if (!fa[v]) fa[v] = v;
            if (find(u) == find(v))
                ret.push_back(true);
            else
                ret.push_back(false);
        }
    }
    for (int i = ret.size() - 1; i >= 0; i--)
    {
        if (ret[i])
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}



//5.小美的区间删除
//小美拿到了一个大小为n的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有k个 0。
//小美想知道，一共有多少种不同的删除方案？

#include <iostream>
#include <vector>
using namespace std;

int n, k;

int kzero(vector<int>& prev_two, vector<int>& prev_five, int left, int right)
{
    return min(prev_five[n] - prev_five[right] + prev_five[left - 1], prev_two[n] - prev_two[right] + prev_two[left - 1]);
}


int main()
{
    cin >> n >> k;
    vector<int> x(n + 1, 0);
    vector<int> prev_two(n + 1, 0);
    vector<int> prev_five(n + 1, 0);
    for (int i = 1; i <= n; i++)   cin >> x[i];

    //统计5与2的前缀和
    for (int i = 1; i <= n; i++)
    {
        int  five = 0, two = 0;
        while (x[i] % 5 == 0)
        {
            x[i] /= 5;
            five++;
        }
        while (x[i] % 2 == 0)
        {
            x[i] /= 2;
            two++;
        }
        prev_two[i] = prev_two[i - 1] + two;
        prev_five[i] = prev_five[i - 1] + five;
    }
    int l = 0, r = 0;
    long long ans = 0;
    //搜素
    for (int i = 1, j = 1; i <= n && j <= n;)
    {
        //找到或 i=j+1
        while (j <= n && kzero(prev_two, prev_five, i, j) >= k) j++;
        //[i,j-1]有效  || i==j则 [i,i]不符合
        ans += 1LL * (j - i) * (j - i + 1) / 2;
        //重合  删除 [i,r-1]
        if (r >= i)
            ans -= 1LL * (r - i) * (r - i + 1) / 2;
        l = i, r = j;    //更新区间
        //搜索
        while (i <= j && kzero(prev_two, prev_five, i, j) < k)
            i++;
        j = max(i, j);
    }
    cout << ans;
    return 0;
}
